﻿
using System.Collections;

namespace eightnum
{
        #region 棋盘数据结构
        /// <summary>
        /// 空格移动的方向
        /// </summary>
        public enum Direction
        {
            None,
            Up,
            Left,
            Right,
            Down
        }

        /// <summary>
        /// 返回答案
        /// </summary>
        public enum Answer
        {
            /// <summary>
            /// 不存在解答
            /// </summary>
            NotExist,
            /// <summary>
            /// 存在解答
            /// </summary>
            Exist,
            /// <summary>
            /// 在当前指定的搜索深度内不存在解答（需要扩大深度）
            /// </summary>
            NotExistInDepth
        }

        /// <summary>
        /// 局面状态信息
        /// </summary>
        public class StateMsg
        {
            /// <summary>
            /// 深度
            /// </summary>
            public int depth;
            /// <summary>
            /// 方向
            /// </summary>
            public Direction dir;
            /// <summary>
            /// 局面信息类构造函数
            /// </summary>
            /// <param name="depth">深度</param>
            /// <param name="dir">方向</param>
            public StateMsg(int depth, Direction dir)
            {
                this.depth = depth;
                this.dir = dir;
            }
        }

        /// <summary>
        /// 局面状态
        /// </summary>
        public class Node : StateMsg
        {           
            /// <summary>
            /// 棋盘的编码
            /// </summary>
            public int code;
            /// <summary>
            /// 估计值
            /// </summary>
            public int evalue;
            /// <summary>
            /// 指向上一层结点
            /// </summary>
            public Node parentNode;
            /// <summary>
            /// 是否达到目标
            /// </summary>
            public bool Goal;
            /// <summary>
            /// 构造函数，初始化结点
            /// </summary>
            /// <param name="code">一个用整形表示的棋盘</param>
            /// <param name="evalue">估价值</param>
            /// <param name="depth">深度</param>
            /// <param name="dir">方向</param>
            /// <param name="n">父节点</param>
            public Node(int code,int evalue, int depth, Direction dir,Node n,bool goal)
                : base(depth, dir)
            {
                this.code = code;
                this.evalue = evalue;
                parentNode = n;
                Goal = goal;
                
            }
        }
        public class SortedArrayList : ArrayList 
        {
            /// <summary>
            /// 估价值
            /// </summary>
            public const int EVALUE = 1;
            /// <summary>
            /// 棋盘值
            /// </summary>
            public const int CODE = 2;
            /// <summary>
            /// 加入结点并排序
            /// </summary>
            public bool AddSorted(Node n,int MODE)
            {
                if (MODE == EVALUE)
                {
                    int i, j;
                    for (i = 0, j = Count - 1; i <=j; )
                    {
                        if (n.evalue == ((Node)this[(i + j) / 2]).evalue)
                        {
                            Insert((i + j) / 2, n);
                            return true ;
                        }
                        if (n.evalue > ((Node)this[(i + j) / 2]).evalue) i = (i + j) / 2 + 1;
                        else j = (i + j) / 2 - 1;
                    }
                    Insert(i, n);
                    return true;
                }
                else 
                {
                    int i, j;
                    for (i = 0, j = Count - 1; i <=j; )
                    {
                        if (n.code == ((Node)this[(i + j) / 2]).code)
                        {
                            return false;
                        }
                        if (n.code > ((Node)this[(i + j) / 2]).code) i = (i + j) / 2 + 1;
                        else j = (i + j) / 2 - 1;
                    }
                    Insert(i, n);
                    return true;
                }
            }

        }


        #endregion
    
    
    class AIcores
    {
        #region 常量定义与非核心变量

        /// <summary>
        /// ten[i]代表10的i次方
        /// </summary>
        private static readonly long[] tens = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
        
        #endregion


        /// <summary>
        /// 整个棋盘每个位置可能移动的方向
        /// </summary>
        private readonly Direction[][] dirs;
        /// <summary>
        /// 开始棋盘
        /// </summary>
        private int startBoard;
        /// <summary>
        /// 结束棋盘
        /// </summary>
        private static int endBoard;
        /// <summary>
        /// 结束棋盘数组表示方式
        /// </summary>
        private static readonly int[] endBoardArray=new int[9];
        
        
        
        /// <summary>
        /// 已访问的结点数
        /// </summary>
        public int nodes;

        /// <summary>
        /// A*算法用的OPEN表，自动加入结点后进行排序
        /// </summary>
        public SortedArrayList axOpenList = new SortedArrayList();
        /// <summary>
        /// visited表，存放访问过的结点
        /// </summary>
        public SortedArrayList visitedList = new SortedArrayList();
        /// <summary>
        /// 广度优先搜索的OPEN表
        /// </summary>
        public Queue broadOpenList=new Queue();
        /// <summary>
        /// 储存最终的最短路径
        /// </summary>
        public ArrayList result=new ArrayList();


        /// <summary>
        /// 构造函数初始化dirs
        /// </summary>
        public AIcores()
        {
            dirs = new Direction[9][];
            dirs[0] = new Direction[] { Direction.Right, Direction.Down };
            dirs[1] = new Direction[] { Direction.Left, Direction.Right, Direction.Down };
            dirs[2] = new Direction[] { Direction.Left, Direction.Down };
            dirs[3] = new Direction[] { Direction.Up, Direction.Right, Direction.Down };
            dirs[4] = new Direction[] { Direction.Up, Direction.Left, Direction.Right, Direction.Down };
            dirs[5] = new Direction[] { Direction.Up, Direction.Left, Direction.Down };
            dirs[6] = new Direction[] { Direction.Up, Direction.Right };
            dirs[7] = new Direction[] { Direction.Left, Direction.Right, Direction.Up };
            dirs[8] = new Direction[] { Direction.Up, Direction.Left };
        }



        public static Node MoveBlank(Node node, Direction dir)
        {
            var newNode=new Node(0,0,node.depth+1,dir,node,false);
            int num;
            int t0;
            long t1;
            long t2;
            switch (dir)
            {
                case Direction.Left:
                    newNode.code = node.code - 1;
                    if (newNode.code == endBoard)
                    {
                        newNode.Goal = true;
                        return newNode;
                    }
                    newNode.evalue = evalueFun(newNode.code,newNode.depth)+node.depth;
                    return newNode;
                case Direction.Right:
                    newNode.code = node.code + 1;
                    if (newNode.code == endBoard)
                    {
                        newNode.Goal = true;
                        return newNode;
                    }//得到目标了
                    newNode.evalue = evalueFun(newNode.code, newNode.depth) + node.depth;
                    return newNode;
                case Direction.Up:
                    num = node.code;
                    t0 = 9 - num % 10 + 1;
                    t1 = num / tens[t0];
                    t2 = t1 % 1000;
                    t1 = t1 - t2 + (t2 % 100) * 10 + t2 / 100;
                    t1 *= tens[t0];
                    newNode .code = (int)(t1 + ((num % tens[t0]) - 3));
                    if (newNode.code == endBoard)
                    {
                        newNode.Goal = true;
                        return newNode;
                    }
                    newNode.evalue = evalueFun(newNode.code, newNode.depth) + node.depth;
                    return newNode;
                case Direction.Down:
                    num = node.code; 
                    t0 = 9 - num % 10 + 1 - 3;//跟Up不同的地方
                    t1 = num / tens[t0];
                    t2 = t1 % 1000;
                    t1 = t1 - t2 + (t2 % 10) * 100 + t2 / 10;//跟Up不同的地方
                    t1 *= tens[t0];
                    newNode.code = (int)(t1 + ((num % tens[t0]) + 3));//跟Up不同的地方
                    if (newNode.code == endBoard)
                    {
                        newNode.Goal = true;
                        return newNode;
                    }
                    newNode.evalue = evalueFun(newNode.code, newNode.depth) + node.depth;
                    return newNode;
                default:
                    return null;
            }

        }
        /// <summary>
        /// 恢复上一步的局面
        /// </summary>
        /// <param name="node"></param>
        /// <param name="dir"></param>
        public static Node MoveBack(Node node, Direction dir)
        {
            return MoveBlank(node, (Direction)(5 - dir));
        }

        /// <summary>
        /// 将结果放入resultNode集合中
        /// </summary>
        /// <param name="resultNode">最中的目标结点</param>
        public void setResult(Node resultNode) 
        {
            result.Clear();//清空原结果
            Node tempNode = resultNode ;
            while (tempNode.parentNode != null)
            {
                result.Add(tempNode);
                tempNode = tempNode.parentNode;
            }
        }
        //核心算法
        #region A*算法

        /// <summary>
        /// 距离
        /// </summary>
        /// <param name="t">要移动的结点</param>
        /// <param name="pos">当前位置</param>
        /// <returns></returns>
        public static int distance(int t, int pos)
        {
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                {
                    if (t != endBoardArray[i * 3 + j])
                        return (pos / 3 - i) + (pos % 3 - j);
                }
            return -1;
        }
        /// <summary>
        /// 估价函数
        /// </summary>
        /// <param name="curboard"></param>
        /// <param name="dep"></param>
        /// <returns></returns>
        public static int evalueFun(int curboard,int dep)
        {
            int table = curboard;
            int emptyPos = curboard % 10;
            int ev = 0;
            //写2个for是为了减少9个if
            for (int i = 9; i > emptyPos; i--)
            {
                table /= 10;
                if (table % 10 != endBoardArray[i - 1])
                    ev += distance(table % 10, i);
            }
            for (int i = emptyPos - 1; i >= 1; i--)
            {
                table /= 10;
                if (table % 10 != endBoardArray[i - 1])
                    ev += distance(table % 10, i);
            }
            return ev+dep;
        }
        private int extendAxOpenList() 
        {
            var openNode = (Node)axOpenList[0];
            axOpenList.RemoveAt(0);
            int flag = 0;
            int emptyPos = openNode.code % 10-1;

           // if (!visitedList.AddSorted(openNode, SortedArrayList.CODE))
            //    return flag;
            foreach (Direction dir in dirs[emptyPos])
            {
                Node tempNode = MoveBlank(openNode, dir);
         
                if (tempNode.Goal)
                {
                    setResult(tempNode);
                    return 2;//达到目标
                }
                if (tempNode == null) return flag;//结点不能展开
                if (visitedList.AddSorted(tempNode, SortedArrayList.CODE))//未访问
                {
                    axOpenList.AddSorted(tempNode, SortedArrayList.EVALUE);
                    flag = 1;
                }

            }
            
            return flag;
        }
        /// <summary>
        /// A*算法
        /// </summary>
        /// <param name="sCode">初始棋盘状态</param>
        /// <param name="dCode">目标棋盘状态</param>
        /// <param name="maxDepth">扩展最大深度</param>
        /// <returns></returns>
        public int Ax(int[,] sCode,int[,] dCode,int maxDepth )
        {
            nodes = 0;
            #region 初始化startboard和endboard
            string codeString1="";
            string codeString2 = "";
            int sEmpty=0;
            int dEmpty=0;
            for(int i=0;i<3;i++)
                for (int j = 0; j < 3; j++)
                {
                    if (sCode[i, j] != 0)
                    {
                        codeString1 += sCode[i, j].ToString();
                    }
                    else
                    {
                        sEmpty = i * 3 + j;

                    }
                    if (dCode[i, j] != 0)
                    {
                        codeString2 += dCode[i, j].ToString();
                    }
                    else
                    {
                        dEmpty = i * 3 + j;

                    }
                    endBoardArray[i * 3 + j] = dCode[i, j];
                }
            startBoard = int.Parse(codeString1)*10+sEmpty+1;
            endBoard = int.Parse(codeString2) * 10 + dEmpty+1;
            if( startBoard==endBoard)return 2;
            #endregion

            var newNode = new Node(startBoard,evalueFun(startBoard,0), 0, Direction.None, null,false);
            axOpenList.AddSorted(newNode, SortedArrayList.EVALUE);
            visitedList.AddSorted(newNode, SortedArrayList.CODE);
            while (axOpenList.Count > 0)
            {
                int flag;
                if ((flag = extendAxOpenList()) == 1) nodes++;
                else if (flag == 2) return 2;//返回成功
            }

            return -1;
        }

        #endregion
        #region 广度优先算法
        /// <summary>
        /// 扩展结点
        /// </summary>
        /// <returns>扩展结果</returns>
        private int extendBroadOpenList()
        {
            var openNode = (Node)broadOpenList.Dequeue();
            int flag = 0;
            int emptyPos = openNode.code % 10 - 1;

            foreach (Direction dir in dirs[emptyPos])
            {
                Node tempNode = MoveBlank(openNode, dir);

                if (tempNode.Goal)
                {
                    setResult(tempNode);
                    return 2;//达到目标
                }
                if (tempNode == null) return flag;//结点不能展开
                if (visitedList.AddSorted(tempNode, SortedArrayList.CODE))//未访问
                {
                    broadOpenList.Enqueue(tempNode);
                    flag = 1;
                }

            }

            return flag;
        }
        /// <summary>
        /// 广度优先算法
        /// </summary>
        /// <param name="sCode">初始棋盘状态</param>
        /// <param name="dCode">目标棋盘状态</param>
        /// <param name="maxDepth">扩展最大深度</param>
        /// <returns></returns>
        public int broad(int[,] sCode, int[,] dCode, int maxDepth) 
        {
            nodes = 0;
            #region 初始化startboard和endboard
            string codeString1 = "";
            string codeString2 = "";
            int flag=0;
            int sEmpty = 0;
            int dEmpty = 0;
            for (int i = 0; i < 3; i++)
                for (int j = 0; j < 3; j++)
                {
                    if (sCode[i, j] != 0)
                    {
                        codeString1 += sCode[i, j].ToString();
                    }
                    else
                    {
                        sEmpty = i * 3 + j;

                    }
                    if (dCode[i, j] != 0)
                    {
                        codeString2 += dCode[i, j].ToString();
                    }
                    else
                    {
                        dEmpty = i * 3 + j;

                    }
                    endBoardArray[i * 3 + j] = dCode[i, j];
                }
            startBoard = int.Parse(codeString1) * 10 + sEmpty + 1;
            endBoard = int.Parse(codeString2) * 10 + dEmpty + 1;
            if (startBoard == endBoard) return 2;
            #endregion

            var newNode = new Node(startBoard, evalueFun(startBoard,0), 0, Direction.None, null, false);
            broadOpenList.Enqueue(newNode);
            visitedList.AddSorted(newNode, SortedArrayList.CODE);
            while (broadOpenList.Count > 0)
            {
                if ((flag = extendBroadOpenList()) == 1) nodes++;
                else if (flag == 2) return 2;//返回成功
            }

            return flag;
        }

        #endregion
    }
}
